UVa/12322 - Handgun Shooting Sport/gen.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 bool point_in_box(double x, double y,
  28                   double x0, double y0,
  29                   double x1, double y1){
  30   return
  31     min(x0, x1) <= x && x <= max(x0, x1) &&
  32     min(y0, y1) <= y && y <= max(y0, y1);
  33 }
  34
  35 int direction(int x1, int y1, int x2, int y2, int x3, int y3) {
  36     return (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
  37 }
  38
  39 bool segment_segment_intersection(int x1, int y1,
  40                                   int x2, int y2,
  41
  42                                   int x3, int y3,
  43                                   int x4, int y4){
  44
  45     int d1 = direction(x3, y3,   x4, y4,   x1, y1);
  46     int d2 = direction(x3, y3,   x4, y4,   x2, y2);
  47     int d3 = direction(x1, y1,   x2, y2,   x3, y3);
  48     int d4 = direction(x1, y1,   x2, y2,   x4, y4);
  49     bool b1 = d1 > 0 and d2 < 0 or d1 < 0 and d2 > 0;
  50     bool b2 = d3 > 0 and d4 < 0 or d3 < 0 and d4 > 0;
  51     if (b1 and b2) return true;
  52     if (d1 == 0 and point_in_box(x1, y1,     x3, y3, x4, y4))
  53         return true;
  54
  55     if (d2 == 0 and point_in_box(x2, y2,     x3, y3, x4, y4))
  56         return true;
  57
  58     if (d3 == 0 and point_in_box(x3, y3,     x1, y1, x2, y2))
  59         return true;
  60
  61     if (d4 == 0 and point_in_box(x4, y4,     x1, y1, x2, y2))
  62         return true;
  63
  64     return false;
  65 }
  66
  67 int main(){
  68     int times = 100;
  69     const int MAXCOORD = 1000;
  70     while (times--) {
  71         int B = rand() % 100 + 1;
  72         vector< pair< pair<int, int>, pair<int, int> > > segments;
  73         for (int i = 0; i < B; ++i) {
  74             while (true) {
  75                 int x0 = (rand() % MAXCOORD) * (rand() % 2 == 0 ? 1 : -1);
  76                 int y0 = (rand() % MAXCOORD) + 1;
  77                 int x1 = (rand() % MAXCOORD) * (rand() % 2 == 0 ? 1 : -1);
  78                 int y1 = (rand() % MAXCOORD) + 1;
  79                 if (x0 * y1 - x1 * y0 == 0) continue;
  80                 bool intersect = false;
  81                 for (int i = 0; i < segments.size() and !intersect; ++i) {
  82                     intersect |= segment_segment_intersection(x0, y0, x1, y1,     segments[i].first.first, segments[i].first.second, segments[i].second.first, segments[i].second.second);
  83                 }
  84                 if (intersect) continue;
  85                 segments.push_back(make_pair( make_pair(x0, y0),  make_pair(x1, y1)   ));
  86                 break;
  87             }
  88         }
  89         assert(segments.size() == B);
  90         printf("%d\n", B);
  91         for (int i = 0; i < B; ++i) {
  92             printf("%d %d %d %d\n", segments[i].first.first, segments[i].first.second, segments[i].second.first, segments[i].second.second);
  93         }
  94     }
  95     puts("0");
  96     return 0;
  97 }